
// 1035.不相交的线
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        // 此题就是求两个数组的最长公共子序列
        int n1 = nums1.size() , n2 = nums2.size();
        // 使用一个二维DP表来完成 , dp[i][j] 表示 nums1中[0,i]和nums2中[0,j]最长公共子序列的长度

        vector<vector<int>> dp(n1 + 1 , vector<int>(n2 + 1));
        int ret = 0; 
        for(int i = 1 ; i <= n1 ; i++)
        {
            for(int j = 1 ; j <= n2 ; j++)
            {
                if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i][j - 1] , dp[i - 1][j]);
            }
        }
        return dp[n1][n2];
    }
};